//
// Created by LiuYou on 2021/12/6.
//

#include <iostream>
#include <algorithm>
#include <random>
#include <iterator>


static int random(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


int main(int argc, char** argv) {
    std::cout << "============================[ 构建堆 ]===============================" << std::endl;
    {
        std::vector<int> arr;
        arr.reserve( 10 );

        for (int i = 0; i < 10; ++i) {
            arr.emplace_back( random( 0, 100 ));
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        // todo 笔记: make_heap(); 默认使用的是<运算符, 即 std::less<>()。 生成的是一个大顶堆。
        std::make_heap( arr.begin(), arr.end());

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;
    }

    std::cout << "============================[ 构建堆 ]===============================" << std::endl;
    {
        std::vector<int> arr;
        arr.reserve( 10 );

        for (int i = 0; i < 10; ++i) {
            arr.emplace_back( random( 0, 100 ));
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        // todo 笔记: make_heap(); 默认生成的是一个大顶堆, 而如果指定了第三个参数 comp, 即仿函数 为 std::greater<>()
        //  的话, 那么就是将序列构建为了一个小顶堆。
        std::make_heap( arr.begin(), arr.end(), std::greater<>());

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;
    }

    std::cout << "============================[ 构建堆 ]===============================" << std::endl;
    {
        std::vector<int> arr;
        arr.reserve( 10 );

        for (int i = 0; i < 10; ++i) {
            arr.emplace_back( random( 0, 100 ));
        }

        std::cout << "源序列: ";
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        std::make_heap( arr.begin(), arr.end());

        std::cout << "大顶堆: ";
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        std::make_heap( arr.begin(), arr.end(), std::greater<>());

        std::cout << "小顶堆: ";
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;
    }


    std::cout << "============================[ 堆操作 ]===============================" << std::endl;
    {
        std::vector<int> arr;
        arr.reserve( 10 );

        for (int i = 0; i < 10; ++i) {
            arr.emplace_back( random( 0, 100 ));
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "是堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << std::endl;
        std::cout << std::endl;

        std::make_heap( arr.begin(), arr.end());

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "是堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << std::endl;
        std::cout << std::endl;

        // push_heap();
        arr.emplace_back( 101 );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "是堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << std::endl;
        std::cout << std::endl;

        std::push_heap( arr.begin(), arr.end());
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "是堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << std::endl;
        std::cout << std::endl;

        // pop_heap();
        std::pop_heap( arr.begin(), arr.end());
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "是堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << std::endl;
        std::cout << std::endl;

        arr.pop_back();
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "是堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << std::endl;
        std::cout << std::endl;

        // 默认的话是将大顶堆进行排序, 排序的结果是 升序。
        // 那么应该排序的过程类似于我自己写的 heapify();函数。
        std::sort_heap( arr.begin(), arr.end());
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "是堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << std::endl;
        std::cout << std::endl;
    }


    std::cout << "============================[ 堆排序 ]===============================" << std::endl;
    {
        std::vector<int> arr;
        arr.reserve( 10 );

        for (int i = 0; i < 10; ++i) {
            arr.emplace_back( random( 0, 100 ));
        }
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "是堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << std::endl;

        std::make_heap( arr.begin(), arr.end());
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "是堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << std::endl;

        // 对大顶堆进行排序。
        // todo 笔记: 对大顶堆调用 sort_heap();进行排序会是 升序。
        std::sort_heap( arr.begin(), arr.end());
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end()) << std::endl;

        // 对小顶堆进行排序。
        std::cout << "------------------" << std::endl;
        std::make_heap( arr.begin(), arr.end(), std::greater<>());
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "是堆: " << std::boolalpha << std::is_heap( arr.begin(), arr.end()) << std::endl;

        // todo 笔记: 对小顶堆调用 sort_heap();进行排序会是 降序。
        std::sort_heap( arr.begin(), arr.end(), std::greater<>());
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << "有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end(), std::greater<>()) << std::endl;
    }

    /*
     *todo 笔记: 标准库提供的堆操作接口:
     * make_heap();
     * push_heap();要和 emplace_back();/push_back();配合使用。
     * pop_heap();要和 pop_back();配合使用。
     * is_heap();
     * sort_heap();
     */


    return 0;
}
